package bank;

public class _60GetPermutation {
    static StringBuilder target = new StringBuilder();
    static StringBuilder res = new StringBuilder();
    public static String getPermutation(int n, int k) {
        /**
         * n = 3,k = 5
         * 123 132 213 231 312 321
         * answer = 312
         */
        for (int i = 0;i < n;i++){
            target.append(i+1);
        }
        recursion(target,n,k);
        return res.toString();
    }

    private static void recursion(StringBuilder target, int n, int k) {
        while (n > 0){
            int judge = factorial(n-1);
            if (k % judge == 0){
                //  如果k可以被judge整除
                res.append(target.charAt(k / judge - 1));
                target.deleteCharAt(k / judge - 1);
                res.append(target.reverse());
                return;
            }
            if (k > judge){
                res.append(target.charAt(k / judge));
                target.deleteCharAt(k / judge);
                k %= judge;
            }else {
                res.append(target.charAt(0));
                target.deleteCharAt(0);
            }
            n--;
        }
    }

    private static int factorial(int n){
        int res = 1;
        for (int i = 1;i <= n;i++){
            res *= i;
        }
        return res;
    }
}
